Булева функция

**Логической переменной** будем называть переменную $x$, принимающую значения $0$ и $1$

**Булевой функцией** от $n$ переменных называется функция $f \mathpunct{:} \{0,1\}^n \to \{0,1\}$ $2^{2^n}$ — количество булевых функций на $n$ переменных

Переменная $x_i$ функции $f(x_1, \dots, x_n)$ называется **фиктивной**, если $$f(x_1, \dots, x_{i-1}, 0, x_{i+1}, \dots, x_n) = f(x_1, \dots, x_{i-1}, 1, x_{i+1}, \dots, x_n)$$ при любых значениях $x_j$ ($j \neq i$)

Пусть даны $f(x_1, \dots, x_n)$ и $x_1 = g_1(t_1, \dots, t_m), \dots, x_n = g_n(t_1, \dots, t_m)$. Делаем подстановку и получаем функцию: $$h(t_1, \dots, t_m) = f(g_1(t_1, \dots, t_m), \dots, g_n(t_1, \dots, t_m))$$